Granularidad
Es determinada por el número de tareas (=CPUs trabajando) y el tamaño del problema asignado a cada tarea.
Fine-grained (grano fino): muchas tareas, pequeños problemas
Coarse-grained (grano grueso): pocas tareas más grandes.
Grado de concurrencia
Es el máximo número de tareas que corren en paralelo en un algoritmo.
Puede ser menor que número de CPUs asignadas, por dependencia de las tareas.
Grado promedio de concurrencia: número promedio de tareas en paralelo en un momento dado.
Generalmente, grano fino ? más concurrencia
Conc.promedio= (4*10+2*6+1*11)/27=2.33 Conc.Promedio=(4*10+6+11+7)/34=1.88
Ruta crítica y grafo de interacción de tareas
Ruta crítica: es la más larga ruta entre nodos iniciales y finales del grafo. En el ejemplo anterior (a) 10+9+8=27 (b) 10+6+11+7=34
En el grafo, los nodos representan tareas y las aristas conectan tareas que interactúan unas con otras.
Pesos de los nodos: tiempo de cómputo. Pesos de aristas: costo de interacción (ej.: comunicación).
Ejemplo: multiplicación vector x matriz dispersa (sparse)
Computar:
Solo para los A[i,j] ? 0. Suponer que hay n CPUs y se reparten las
filas de A y los valores de b (ej.: CPU0 es dueña de b[0])
Mapeo
Es el mecanismo por el que las tareas se asignan a los procesos
Un proceso: proceso como se entiende en sistemas operativos, o parte de un proceso (hilo)
Generalmente 1 proceso ??1 CPU/ core
Ejemplo
Técnicas de descomposición
Más conocidas:
Descomposición Recursiva
Descomposición de datos
Descomposición Exploratoria
Descomposición Especulativa
Las 2 primeras son más generales.
D. Recursiva
Divide y vencerás, en forma recursiva
Ej. quicksort
Ej: hallar mínimo número de un array A de n elementos
Serial o secuencial:
1. procedure SERIAL_MIN (A, n)
2. begin
3. min = A[0];
4. for i := 1 to n – 1 do
5. if (A[i] < min) min := A[i];
6. endfor;
7. return min;
8. end SERIAL_MIN
Reformado : divide y vencerasEj: A={4,9,1,7,8,11,2,12}
Cambiado a recursivo
1. procedure RECURSIVE_MIN (A, n)
2. begin
3. if (n = 1) then
4. min := A[0];
5. else
6. lmin := RECURSIVE_MIN (A, n/2);
7. rmin := RECURSIVE_MIN (&(A[n/2]), n – n/2);
8. if (lmin < rmin) then
9. min := lmin;
10. else
11. min := rmin;
12. endelse;
13. endelse;
14. return min;
15. end RECURSIVE_MIN
A un CPU
A otro CPU
D. De datos
Primero se particiona la data
Luego se usa esa partición de la data para inducir la partición de las computaciones en tareas.
Lo ideal sería que ambas particiones sean parejas en tamaño (cada proceso / CPU / core con data parecidas en tamaño y tareas parecidas en tiempo de cómputo)
Ej: multiplicación de matrices
Parta cada factor en 4 submatrices. El resultado también.
Cada submatriz del resultado se puede calcular por separado.
Y que pasa si tengo 8 CPUs?
Ej: calcular frecuencias de itemsets en una tabla
Particionando data intermedia
D. exploratoria
Se usan en problemas de búsqueda (ej.: en árboles)
Se parte el espacio de búsquedas en subespacios más pequeños.
Ej: puzzle de 15 cuadrados
D. especulativa
Cuando en un algoritmo hay ramas que dependen de un IF (si es verdadero se hace una operación, si es falso se hace otra), se puede paralelizar ambas tareas ANTES de poder evaluar el IF, ejecutando ambas operaciones y esperar al IF para eliminar una y mantener la otra.
Ejemplo
x=valoresPropios(matriz A)
IF max(x)< 1
B=C+D
ELSE
B=X-Y
Tareas
Características de las tareas:
Generación: estática o dinámica
Tamaño: uniforme o no uniforme
Conocimiento del tamaño: se puede conocer de antemano o no?
Tamaño de la data asociada a las tareas
Interacciones entre tareas
Características:
Estáticas vs Dinámicas
Regular vs Irregular
Read-only vs. Read-Write
1-way vs 2-way. Todas las read only son 1-way, pero las read-write pueden ser de cualquier tipo.
Ej. Regular: gradiente de una imagen para ver “bordes”
Mapeo para balance de carga
Dos objetivos
Reducir tiempo de interacción entre procesos
Reducir el tiempo ocioso de los procesos
Mutuamente excluyentes
Mapeo estático vs dinámico
Esquemas de mapeo estático
Mapeos basados en la partición de data para arrays:
Bloques 1-D, 2-D, 3-D
Ciclicos
Aleatorios en bloque
Basados en grafos:
Bloques
Cíclicos
Grafo de un lago, mapeo en 8 procesos
Mapeos basados en dependencia de tareas
Mapeo dinámico
Centralizado: un master reparte las tareas a los procesos según su criterio. Tareas de una en una, o en chunks (“pedazos”)
Distribuido: un proceso puede enviar o recibir las tareas de otro. Si P3 tiene mucha carga, delega algunas tareas a P7 que esta libre.
Localidad
Grado en el que la data que reside en memoria de un CPU basta para el trabajo de esa CPU. Mientras más tenga que usar data “ajena”, menos localidad hay.
En otros ramos de Computer Science tiene otros significados
Paralelismo y Localidad en Simulación
Problemas físicos tienen paralelismo y localidad:
Muchos objetos operan independientemente unos de otros.
Los objetos generalmente dependen más de otros objetos cercanos que de los lejanos.
Dependencia en objetos lejanos se puede simplificar.
Algunos modelos científicos pueden crear paralelismo:
Cuando un problema continuo se discretiza, la dependencia en el tiempo se limita a time steps cercanos.
Efectos lejanos se pueden ignorar o aproximar.
Puede haber paralelismo en varios niveles
Ej.: varios circuitos se pueden simular a diferentes niveles, desde el de todo un aparato, hasta los componentes básicos individuales.
Algunas clases básicas de simulación
Sistemas de eventos discretos:
Ejs: “Game of Life,” circuitos lógicos.
Sistemas de partículas:
Ejs: bolas de billar, dispositivos semiconductores, galaxias.
Variables agregadas que dependen de param. continuos:
EDOs, ej: simulación de circuitos (Spice), estructuras mecánicas, cinética química.
Variables continuas que dependen de param. continuos:
EDPs, ej: calor, elasticidad, electrostática.
Muchas simulaciones combinan varias técnicas.
Resumen
Eventos discretos
Tiempo y espacio discretos
Partículas
Caso especial de sistema agregado
Ec. Diferenciales ordinarias (EDOs)
Sistemas agregados
Entidades o posiciones discretas, tiempo continuo
Ec. Diferenciales parciales (EDPs)
Tiempo y espacio es continuo
Identificar problemas comunes y sus soluciones
discreto
continuo
Maximizando localidad de data
Minimizar el volumen de intercambio de data. Ej.: gradiente, partir en 4 procesos como cuatro cuadrados pequeños vs 4 tiras largas
Minimizar la frecuencia de interacciones. Ej.: multiplicacion vector matriz dispersa, con núm.CPUs < < núm. de filas
Minimizar congestión y hot spots
Si 2 o más procesos quieren usar la misma data a la vez, donde por lo menos 1 de ellos quiere escribir: contención. Mientras ese lea+escriba, los otros no deberían correr.
Cambiar el patrón de acceso (orden de las operaciones)
Que coincidan computaciones e interacciones
Ej: mientras P0, P1 computan, P2 lee y/o escribe la variable x. Luego le tocara a P0.
Otro ej.: usar comunicación asíncrona
Modelos de algoritmos paralelos
Modelo data-parallel: ej.sumatoria
Modelo gráfico de tareas: ej. Multp. Vector matriz dispersa
Modelo de pool de tareas: mapeo dinámico de un loop es muchos sub-loops
Modelo master-slave. Ej: montecarlo maestro esclavo
Modelo pipeline o productor-consumidor
Híbridos
 Página anterior | Volver al principio del trabajo | Página siguiente  |